<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
The LP Model
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial130.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial132.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc258">18.1</A>&nbsp;&nbsp;The LP Model</H2>
In modeling this problem as a MILP we could choose to introduce a
variable <I>x</I><SUB><I>j</I></SUB> for each feasible way of cutting a board of length
<I>l</I> into boards of length <I>l</I><SUB><I>i</I></SUB> with coefficients <I>a</I><SUB><I>ij</I></SUB>
representing the number of boards of length <I>l</I><SUB><I>i</I></SUB> obtained from the
cutting associated with <I>x</I><SUB><I>j</I></SUB> and a constraint
&Sigma;<SUB><I>j</I>=1</SUB><SUP><I>n</I></SUP><I>a</I><SUB><I>ij</I></SUB><I>x</I><SUB><I>j</I></SUB>&#8805; <I>b</I><SUB><I>i</I></SUB> specifying the number of boards
<I>b</I><SUB><I>i</I></SUB> required for each length <I>l</I><SUB><I>i</I></SUB>; for realistic problems there
will frequently be very many feasible cuttings and associated
variables <I>x</I><SUB><I>j</I></SUB> and as these must be enumerated before problem
solution can begin this approach may be impractical. We could instead
introduce for each stock board used a set of variables <I>x</I><SUB><I>i</I>,<I>j</I></SUB> for
each demand <I>i</I> indicating the cutting required, a variable <I>w</I><SUB><I>j</I></SUB>
representing the resulting waste and a constraint
&Sigma;<SUB><I>i</I>=1</SUB><SUP><I>m</I></SUP><I>l</I><SUB><I>i</I></SUB><I>x</I><SUB><I>i</I>,<I>j</I></SUB> + <I>w</I><SUB><I>j</I></SUB> = <I>l</I> ensuring the cutting is
valid. Although we do not know how many boards will be required in the
optimal solution, we do have an upper bound on this number
<I>K</I><SUB>0</SUB>=&Sigma;<SUB><I>i</I>=1</SUB><SUP><I>m</I></SUP>&lceil;<I>b</I><SUB><I>i</I></SUB>/&lfloor;<I>l</I>/<I>l</I><SUB><I>i</I></SUB>&rfloor;&rceil; and introduce the above variable
sets and constraint for <I>K</I><SUB>0</SUB> boards. The constraints
&Sigma;<SUB><I>j</I>=1</SUB><SUP><I>K</I><SUB>0</SUB></SUP><I>x</I><SUB><I>ij</I></SUB>&#8805; <I>b</I><SUB><I>i</I></SUB> specify the number of boards
<I>b</I><SUB><I>i</I></SUB> required for each length <I>l</I><SUB><I>i</I></SUB>. Since all <I>K</I><SUB>0</SUB> boards may
not be required we introduce a variable <I>x</I><SUB><I>j</I></SUB> denoting whether a
board is used and modify the valid cutting constraint
<DIV CLASS="center"><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP>
</TD>
<TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR><TD ALIGN=center NOWRAP><I>m</I></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><FONT SIZE=5>&Sigma;</FONT></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><I>i</I>=1</TD>
</TR></TABLE></TD>
<TD NOWRAP><I>l</I><SUB><I>i</I></SUB><I>x</I><SUB><I>ij</I></SUB>+<I>w</I><SUB><I>j</I></SUB>=<I>lx</I><SUB><I>j</I></SUB>
</TD>
</TR></TABLE></DIV>
so that unused boards have zero cost in the objective function. The complete problem formulation is then:
<DIV CLASS="center"><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP >
</TD>
<TD NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=right NOWRAP><B><I>P</I>:</B> <I>minimize</I> <I>z</I></TD>
<TD ALIGN=center NOWRAP>=</TD>
<TD ALIGN=left NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR><TD ALIGN=center NOWRAP><I>K</I><SUB>0</SUB></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><FONT SIZE=5>&Sigma;</FONT></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><I>j</I>=1</TD>
</TR></TABLE></TD>
<TD NOWRAP><I>w</I><SUB><I>j</I></SUB></TD>
</TR></TABLE></TD>
</TR>
<TR><TD ALIGN=right NOWRAP>&nbsp;</TD>
<TD ALIGN=center NOWRAP>&nbsp;</TD>
<TD ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD ALIGN=right NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=right NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP ><I>subject</I> <I>to</I> </TD>
<TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR><TD ALIGN=center NOWRAP><I>K</I><SUB>0</SUB></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><FONT SIZE=5>&Sigma;</FONT></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><I>j</I>=1</TD>
</TR></TABLE></TD>
<TD NOWRAP><I>x</I><SUB><I>ij</I></SUB></TD>
</TR></TABLE></TD>
</TR></TABLE></TD>
<TD ALIGN=center NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=center NOWRAP>&#8805;</TD>
</TR></TABLE></TD>
<TD ALIGN=left NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=left NOWRAP><I>b</I><SUB><I>i</I></SUB></TD>
</TR></TABLE></TD>
<TD NOWRAP>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&forall; <I>i</I></TD>
</TR></TABLE></TD>
</TR>
<TR><TD ALIGN=right NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=right NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR><TD ALIGN=center NOWRAP><I>m</I></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><FONT SIZE=5>&Sigma;</FONT></TD>
</TR>
<TR><TD ALIGN=center NOWRAP><I>i</I>=1</TD>
</TR></TABLE></TD>
<TD NOWRAP><I>l</I><SUB><I>i</I></SUB><I>x</I><SUB><I>i</I>,<I>j</I></SUB>+<I>w</I><SUB><I>j</I></SUB></TD>
</TR></TABLE></TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>w</I><SUB><I>j</I></SUB></TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>x</I><SUB><I>i</I>,<I>j</I></SUB></TD>
</TR>
<TR><TD ALIGN=right NOWRAP><I>x</I><SUB><I>j</I></SUB></TD>
</TR></TABLE></TD>
<TD ALIGN=center NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=center NOWRAP>=</TD>
</TR>
<TR><TD ALIGN=center NOWRAP>&isin;</TD>
</TR>
<TR><TD ALIGN=center NOWRAP>&isin;</TD>
</TR>
<TR><TD ALIGN=center NOWRAP>&isin;</TD>
</TR></TABLE></TD>
<TD ALIGN=left NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=left NOWRAP><I>lx</I><SUB><I>j</I></SUB></TD>
</TR>
<TR><TD ALIGN=left NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP>{</TD>
<TD NOWRAP>0,&hellip;,<I>l</I></TD>
<TD NOWRAP>}</TD>
</TR></TABLE></TD>
</TR>
<TR><TD ALIGN=left NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP>{</TD>
<TD NOWRAP>0,&hellip;,<I>h</I><SUB><I>i</I></SUB></TD>
<TD NOWRAP>}</TD>
<TD NOWRAP>&nbsp;&nbsp;&forall; <I>i</I></TD>
</TR></TABLE></TD>
</TR>
<TR><TD ALIGN=left NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP>{</TD>
<TD NOWRAP>0,&nbsp;1</TD>
<TD NOWRAP>}</TD>
</TR></TABLE></TD>
</TR></TABLE></TD>
<TD NOWRAP>&nbsp;&nbsp;</TD>
<TD NOWRAP>&#9131;<BR>
&#9130;<BR>
&#9132;<BR>
&#9130;<BR>
&#9133;</TD>
<TD NOWRAP>&forall; <I>j</I></TD>
</TR></TABLE></TD>
</TR></TABLE></TD>
</TR></TABLE></DIV>
where <I>h</I><SUB><I>i</I></SUB>=&lfloor;<I>l</I>/<I>l</I><SUB><I>i</I></SUB>&rfloor;. This problem formulation is modeled and solved in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>  as follows:
<PRE CLASS="verbatim">
        :- lib(eplex).

        % eplex instance creation
        :- eplex_instance(cut_stock).

        lp_cut_stock(Lengths, Demands, StockLength, Vars, Cost) :-
            (
                foreach(Li, Lengths),
                foreach(Bi, Demands),
                foreach([], XijVars0),
                foreach(Maxi, Bounds),
                fromto(0, KIn, KOut, K0),
                param(StockLength)
            do
                KOut is KIn + fix(ceiling(Bi/floor(StockLength/Li))),
                Maxi is fix(floor(StockLength/Li))
            ),
            (
                for(J, 1, K0),
                foreach(Wj, Obj),
                foreach(Xj:Used, Vars),
                fromto(XijVars0, VIn, VOut, XijVars),
                param(Lengths, StockLength, Bounds)
            do
                cut_stock:integers([Xj,Wj]),
                % Xj variable bounds
                cut_stock:(Xj::0..1),
                % Wj variable bounds
                cut_stock:(Wj::0..StockLength),
                (
                    foreach(Li, Lengths),
                    foreach(Xij, Used),
                    foreach(Li*Xij, Knapsack),
                    foreach(XiVars, VIn),
                    foreach([Xij|XiVars], VOut),
                    foreach(Maxi, Bounds),
                    param(Xj)
                do
                    % Xij variable bounds
                    cut_stock:integers(Xij),
                    cut_stock:(Xij::0..Maxi)
                ),
                % cutting knapsack constraint
                cut_stock:(sum(Knapsack) + Wj =:= StockLength*Xj)
            ),
            (
                foreach(Bi, Demands),
                foreach(Xijs, XijVars)
            do
                % demand constraint
                cut_stock:(sum(Xijs) &gt;= Bi)
            ),
            cut_stock:eplex_solver_setup(min(sum(Obj))),
            % optimization call
            cut_stock:eplex_solve(Cost).
</PRE><HR>
<A HREF="tutorial130.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial132.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
